/*

From: bet@std.sbi.com (Bennett Todd)
Newsgroups: alt.sources
Subject: Othello.c
Date: 22 Jun 1994 03:23:45 GMT
Organization: Salomon Brothers, Inc.

This is a fairly portable program I wrote to play othello for an AI class
back in 1983. I wrote it using DeSmet C, and it has some special PC
optimizations, under #ifdef DeSmet, that are non-portable. You'll need to
blow out the #define DeSmet if you aren't using his C compiler. If your C
compiler gets annoyed at illegal syntax within #if/#endif that isn't being
compiled, then you'll also need to edit out the blocks that are ifdef
DeSmet.

This program uses Alpha-Beta pruning of a minimax lookahead tree. It has a
fairly tweaked board evaluation heuristic, with an edge strategy and so on.
It is possibly over-optimized by modern standards, but this thing plays a
strong game, on a 4.77MHz 8088 in 64K of RAM, with no move taking more than
30 seconds.

-Bennett
bet@sbi.com
*/

/*
 * Othello playing program. Fairly portable if DeSmet isn't defined;
 * defining DeSmet enables some inline-assembler screen wizzery on PCs,
 * using DeSmet C's convention for inline assembler.
 *
 * The code looks a _lot_ better if you display it with tabstops every
 * four spaces, rather than every 8.
 *
 * Written in 1993 by Bennett Todd, with some help by John White, who
 * designed the finite state automaton for edge strategy.
 */

/*

	Plays othello using alpha-beta search.
	Defining DEBUG_LEVEL as 1 sets enhanced error trapping, and
							2 gives run-time statistics
							3 enables enhanced run-time sanity checking
	defining IBMPC generates non-portable PC optimization
	defining DeSmet changes handling of '\n' on input

	Switches:
	-f	gofirst (default=no)
	-bn	allocate n boards: default=64, grows as branching factor*depth
	-dn	look ahead n moves: default is variable, must be greater than 0
	-rn reverse the initial board in various ways:

		-r1 reverse initial board setup; 'o' still goes first
		-r2 reverse initial board setup; 'x' goes first
		-r3  normal initial board setup; 'x' goes first

*/

#include <stdio.h>

#define DEBUG_LEVEL 1
#define DeSmet

/*
	About the following defines:
	BEST and WORST are upper and lower bounds, respectively, on the
		worth of a board.
	MAXSONS is the maximum number of possible moves from any given board,
		used to size the sons array in a board node.
	EMPTY, MINE, and HIS are values for the possible states of a square
		on an othello board. In the original code, they were used as an
		enumerated type, after the fashion of PASCAL. However, during
		the process of optimizing the program, It was observed that
		in the code
			<expression>!=EMPTY
		!=EMPTY doesn't change the logical value of the expression, and
			<expression>==EMPTY is equivalent to !<expression>
		Thus the contents of board cells are sometimes used as boolean
		variables.
		What's worse, many nested if expressions and switch statements
		were removed by using values of board cells as subscripts into
		arrays, a process which altogether exceeded any reasonable bounds
		in the finite state machine found in the function worth.
*/

#define TRUE  1
#define FALSE 0
#define WORST -1000
#define BEST   1000
#define MAXSONS 30
#define EMPTY '\0'
#define MINE  '\1'
#define HIS   '\2'

typedef struct boardtype
{
	struct boardtype *sons[MAXSONS];	/* pointers to descendants	*/
	int val;							/* worth of board position	*/
	char *array[8];						/* the board itself			*/
}
BOARD;

BOARD *freeboards; /* pointer to head of linked list of free boards */

int maxdepth[60]=	/* maxdepth[movenumber] is the depth that alphabeta */
	{				/* will search on the movenumber'th move			*/
		1, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
		3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
		3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
		3, 3, 3, 3, 3, 3, 4, 7, 6, 5, 4, 3, 2, 1, 1
	},
	maxboards=64,	/* default number of boards to allocate 	*/
	reversed=FALSE, /* switch to reverse initial board position */
	movenumber=0,	/* counter for what move we are on			*/
	time_out[3]=	/* timeout points, to hurry up if we are in	*/
	{				/* danger of overshooting 30 seconds		*/
		2000,2500,2800
	},
	start_dive=52,	/* the movenumber on which to switch worths */
	gofirst=FALSE,	/* by default, the opponent goes first		*/
	max,			/* who is playing at any given instant		*/
	(*worth)(),		/* pointer to the current worth function	*/
	i_tran[64]=		/* i subscript generator					*/
	{
		0, 0, 0, 0, 0, 0, 0, 0,
		1, 1, 1, 1, 1, 1, 1, 1,
		2, 2, 2, 2, 2, 2, 2, 2,
		3, 3, 3, 3, 3, 3, 3, 3,
		4, 4, 4, 4, 4, 4, 4, 4,
		5, 5, 5, 5, 5, 5, 5, 5,
		6, 6, 6, 6, 6, 6, 6, 6,
		7, 7, 7, 7, 7, 7, 7, 7
	},
	j_tran[64]=		/* j subscript generator					*/
	{
		0, 1, 2, 3, 4, 5, 6, 7,
		0, 1, 2, 3, 4, 5, 6, 7,
		0, 1, 2, 3, 4, 5, 6, 7,
		0, 1, 2, 3, 4, 5, 6, 7,
		0, 1, 2, 3, 4, 5, 6, 7,
		0, 1, 2, 3, 4, 5, 6, 7,
		0, 1, 2, 3, 4, 5, 6, 7,
		0, 1, 2, 3, 4, 5, 6, 7
	};

long time;			/* time tick holder, for stopwatch	*/

/*
	The array moves, declared below, is an array of pointers to arrays
	of pointers to arrays of subscripts, ranging from 0 to 63.
	A board is declared in the structure declaration above to be represented
	by an array of 8 pointers to arrays of chars (8 per array). In my
	initialization of the board structures, I explicitly allocate the row
	arrays consecutively; therefore, board->array[0] can be taken as a
	pointer to an array 64 long of chars, containing the cells of the board.
	board->array[0][moves[i][j][k]] is the k-th step in th j-th direction
	from the i-th cell in board. Moves is 64 long; moves[i] is variable
	length (one for each direction in which a move is possible) delimited
	with NULLs, and move[i][j] is variable length, delimited by i. In
	other words, to walk as far as possible in the j-th direction from
	cell i, you could use
		for(k=0;i!=moves[i][j][k];k++)
	though I didn't, since I use pointers to walk through the array.

*/

char **moves[64],
	 print_chars[3]={' ','x','o'}; /* the character to print for a cell */

#if DEBUG_LEVEL > 1
int allsons_called,
	worth_called,
	max_used_boards,
	boards_in_use,		/* various variables to accumulate statistics */
	greatest_branching,
	alpha_prunes,
	beta_prunes;
#endif
#if DEBUG_LEVEL > 2
	int moves_checksum,
		board_count=0;

	BOARD *board_bottom,
		  *board_end;
#endif

#ifdef IBMPC
	int line_number,		/* the current screen line number	*/
		screen_seg;			/* segment offset for video ram		*/

	char scr_line[160];		/* output line--character data		*/
							/* alternating with attribute bytes */
#if DEBUG_LEVEL > 1
#define BOARD_TOP 960
#else
#define BOARD_TOP 1120
#endif
#endif

main(argc,argv)
int argc;
char **argv;
{
	int i,
		temp,
		worth_1(),	/* necessary declarations to tell the compiler what 	*/
		worth_2(),	/* kind of objects these are, for assignment to worth	*/
		oldmove;

	long time_tick();	/* only implemented on the IBM-PC, a stopwatch		*/

	BOARD *root,			/* the root of the current tree, changed by 	*/
		  *firstboard();	/* both move() and getmove()					*/

#if DEBUG_LEVEL > 1
#ifdef IBMPC
	char *_showsp(),
		 *_memory();
#endif
#endif

	/* parse the switches on the command line	*/
	for(i=1;i<argc;i++)
		/* all of which start with '-'	*/
		if(*argv[i]=='-')
			switch(*++argv[i])
			{
				case 'f':	/* set a boolean switch gofirst, and			*/
				case 'F':	/* exchange how squares are printed				*/
					gofirst=TRUE;
					temp=print_chars[1];
					print_chars[1]=print_chars[2];
					print_chars[2]=temp;
					break;
				case 'd':	/* force depth to be maxdepth for every move	*/
				case 'D':
					if(isdigit(*++argv[i]))
					{
						maxdepth[0]=atoi(argv[i]);
						start_dive=60-maxdepth[0];
						for(temp=0;temp<59;temp++)
							maxdepth[temp+1]=maxdepth[temp];
					}
					else
						fprintf(stderr,"bad depth %s\n",argv[i]);
					break;
				case 'b':	/* change number of boards to allocate			*/
				case 'B':
					if(isdigit(*++argv[i]))
						maxboards=atoi(argv[i]);
					else
						fprintf(stderr,"bad board limit %s\n",argv[i]);
					break;
				case 'r':	/* reverse board position in various ways		*/
				case 'R':
					if(isdigit(*++argv[i]))
					{
						temp=atoi(argv[i]);
						if(temp%2)
							reversed=TRUE;
						if(temp>1)
						{
							temp=print_chars[1];
							print_chars[1]=print_chars[2];
							print_chars[2]=temp;
						}
					}
					else
						fprintf(stderr,"bad reverse switch %s\n",argv[i]);
					break;
				default:
					fprintf(stderr,"unknown switch %s ignored\n",argv[i]);
					break;
			}
		else
			fprintf(stderr,"unknown arg %s ignored\n",argv[i]);

#ifdef IBMPC
	init_screen();	/* initialize scr_line and screen_seg */
#endif

	/* call various initialization routines			*/
	worth=worth_1;	/* the main heuristic function	*/

#if DEBUG_LEVEL > 1
#ifdef IBMPC
	printf("freespace bottom %u\n",((unsigned int) _memory()));
	printf("    stack    top %u\n",((unsigned int) _showsp()));
#endif
#endif

	initmoves();	/* initialize the array moves	*/

#if DEBUG_LEVEL > 2
	board_bottom=freeboards;
	moves_checksum=check_moves();
#endif

	initfree();			/* set up free boards list	*/

#if DEBUG_LEVEL > 2
	printf("allocated %d boards\n",board_count);
#endif

	root=firstboard();	/* set up to play the game	*/

#if DEBUG_LEVEL > 2
	board_count--;
	printf("which leaves %d to play with.\n",board_count);
#endif

	time=time_tick();	/* and mark time			*/

	if(gofirst)
		move(&root);
	else
	{

#ifdef IBMPC
	clear_home();	/* fast clear screen	*/
#else
	putchar('\f');	/* slow one				*/
#endif

		putboard(root,NULL);	/* put only one board */
	}

	oldmove=(-1); /* dummy out endgame flag, it's only starting now! */

	/* main game loop */
	while(movenumber<60 && movenumber!=oldmove) /* game lasts 60 moves,		*/
	{											/* unless no one can move	*/

#if DEBUG_LEVEL > 2
		if(moves_checksum!=check_moves())
		{
			printf("Moves checksum failed. Sorry, boss.\n");
			exit();
		}
		if(board_count!=count_boards())
			printf("I seem to have mislain a board: %d/%d\n",
					board_count,count_boards());
#endif

		if(movenumber>start_dive)	/* change to h*, the "true" h function	*/
		{
			time_out[0]=time_out[1];
			worth=worth_2;			/* only computable by looking to the end*/
		}
		oldmove=movenumber;			/* set to recognize if no one can move	*/
		getmove(&root);	/* get a move from the user	*/
		move(&root);	/* make a move				*/
	}
	score(root);	/* report the result */
}

/*
	move makes a move on the (called-by-reference) board. It first
	expands all possible moves with a call to allsons, with max set to
	true (moves is trying to maximize the evaluation function), then uses
	alphabeta to evaluate each possibility, picking the best.
	Move is different from alphabeta mostly in that
		a)	it always and only plays as max
		b)	it must keep track of the actual boards, and not just
			their values (alphabeta always reclaims as soon as possible)
		c)	it is in charge of initializing everything for the search
		d)	rather than returning a backed up value, it simply outputs the
			move (and some other junk) and resets the root to point to the
			new move.
*/

move(board)
BOARD **board;
{
	BOARD *tempboard;

	int i,
		n,
		rush=0,			/* used to panic stop short of 30 seconds			*/
		temp,
		alpha=WORST,	/* the root is max, and therefore has an alpha value*/
		best=WORST-1,	/* must be worst than the worst possible value, so	*/
						/* that a move will be picked even if they are all	*/
						/* the worst.										*/
		bestboard;		/* subscript of the best board seen so far			*/

	char *t1,			/* a couple of temporary pointers used to			*/
		 *t2;			/* figure out exactly where I moved.				*/

	long time_tick();	/* stopwatch function, implemented only on the PC	*/

	max=TRUE;	/* let us get this straight, once and for all... */

#ifdef IBMPC
	clear_home();	/* fast clear screen	*/
#else
	putchar('\f');	/* slow one				*/
#endif

	/* read the following as "if( <number of sons found> == 0)"	*/
	if(!(n=allsons(*board)))	/* "==0" is equivalent to "!"	*/
	{
		printf("I cannot move. Your turn.\n");
		putboard(*board,NULL);	/* put the board so that he can see the */
		return;					/* result of his last move				*/
	}

#if DEBUG_LEVEL > 1
	allsons_called=1;
	worth_called=n;
	boards_in_use=max_used_boards=1;	/* initialize variables to	*/
	greatest_branching=n;				/* accumulate statistics	*/
	alpha_prunes=0;
	beta_prunes=0;
#endif

	/* for every son */
	for(i=0;i<n;i++)
	{

		max=FALSE;	/* think as my opponent would think */

		/* if this is better than the best we have seen so far */
		if(best<(temp=alphabeta((*board)->sons[i],maxdepth[movenumber],
								alpha,BEST)))
		{
			best=alpha=temp;
			bestboard=i;
		}

		/* make sure we do not under any circumstances exceed 30 seconds */
		if((time_tick()-time) > time_out[rush])
		{
			if(rush==2)
#if DEBUG_LEVEL > 1
			{
				line_number=0;
				fast_puts("buggering out, on account of lack of time!!");
#endif
				goto outta_here;

#if DEBUG_LEVEL > 1
			}
			printf("I'm hurrying...\n");
#endif

			rush++;
			maxdepth[movenumber]--;
		}
	}

outta_here:
	t1=(*board)->array[0]-1;					/* set up pointers	*/
	t2=(*board)->sons[bestboard]->array[0]-1;	/* for comparison	*/
loop:
	while(*++t1==(*++t2));	/* find different squares			*/
	if(*t1)	/* then this square was flipped, not actually moved */
		goto loop;	/* so keep trying							*/

	/* temp gets the 0-63 subscript of the move */
	temp=t1-(*board)->array[0];

#if DEBUG_LEVEL > 1
	printf("I moved at %c %d in %5.2f seconds\n",
			'a'+j_tran[temp],1+i_tran[temp],((float)(time_tick()-time))/100);
#else
	if((time_tick()-time) < 2990)
		printf("I moved at %c %d in %5.2f seconds\n",
			'a'+j_tran[temp],1+i_tran[temp],((float)(time_tick()-time))/100);
	else
		printf("I moved at %c %d in 29.52 seconds\n",
			'a'+j_tran[temp],1+i_tran[temp]);
#endif

	putboard((*board),(*board)->sons[bestboard]);

#if DEBUG_LEVEL > 1
	if((time_tick()-time) > 3000)
		printf("\7\7\7\7\7\7");
	printf("movenumber: %d choices: %d depth: %d",
			movenumber,n,maxdepth[movenumber]);
#if DEBUG_LEVEL > 2
	printf(" boards available: %d",count_boards()+n);
#endif
	printf("\nallsons called: %d worth called: %d boards used: %d\n",
			allsons_called,worth_called,max_used_boards);
	printf("  alpha prunes: %d  beta prunes: %d       total: %d",
			alpha_prunes,beta_prunes,alpha_prunes+beta_prunes);
	printf(" max branching: %d\n",greatest_branching);
#endif

	/* now reclaim unneeded boards, reset the root, and count this move */
	for(i=0;i<n;i++)
		if(i!=bestboard)
			reclaim((*board)->sons[i]);
	tempboard=(*board)->sons[bestboard];
	reclaim(*board);
	*board=tempboard;
	movenumber++;
}

/*
	alphabeta takes four parameters: the board to evaluate,
	the depth to search, and the current alpha and beta values.
	It returns the worth of the board, obtained by backing up
	the values seen at the bottom of the search.
	It plays maximizing or minimizing, based on the global
	boolean variable max.
*/
	
int alphabeta(current,depth,alpha,beta)
BOARD *current;
int depth,
	alpha,
	beta;
{
	int i,
		n,
		temp,
		best,
		curmax; 	/* contains the current value of the global "max",	*/
					/* negated (to minimize the number of negations)	*/

	BOARD *curson;	/* contains the son being examined currently		*/

	/* if no sons can be found */
	if(!(n=allsons(current)))
	{
		max=!max;						/* then try as the other guy	*/
		if(!(n=allsons(current)))		/* and if he can't move			*/
			return(worth_2(current));	/* return the final value		*/
	}

	best=max?WORST:BEST;	/* start off assuming the worst 	*/
	depth--;				/* keep track of depth				*/
	curmax=!max;			/* and max through recursive calls	*/

	/* for every son */
	for(i=0;i<n;i++)
	{
		max=curmax;
		curson=current->sons[i];

		/*
			This statement does it all. Recurse, propogating correct alpha
			and beta values (only one of which can change at any given node)
			unless of course the recursion has terminated, in which case we
			use the value of the node, as evaluated by worth when allsons
			created the node. Put the value thus obtained into temp, and
			compare it with the best value seen so far. The sense of
			comparison is reversed if curmax is true (bitwise xor is all
			right if both booleans are "pure"--0 or 1).
		*/
		if(curmax^best<(temp=depth?
								(curmax?
									alphabeta(curson,depth,alpha,best)
									:alphabeta(curson,depth,best,beta))
								:curson->val))
		{
			/* check for an alphabeta "prune" of the tree */
			if(curmax?(temp<=alpha):(temp>=beta))
			{

#if DEBUG_LEVEL > 1
				if(curmax)
					beta_prunes++;
				else				/* accumulate statistics */
					alpha_prunes++;
#endif

				while(i<n)						/* clean up			*/
					reclaim(current->sons[i++]);
				return(temp);					/* and pack it in	*/
			}
			else
				best=temp;	/* remember the best value seen so far	*/
		}
		reclaim(curson);
	}
	return(best);
}

/*
	Simple-minded free space management. Keep a bunch of boards on a linked
	list. When one is needed, take it off the top. When no longer needed,
	insert it at the top. Optionally, check for out-of-boards (The converse,
	attempting to check for freeing of space not taken from the freeboard
	list, seemed to be too difficult. Perhaps I could have kept around high-
	water and low-water mark pointers to the space of legal board pointers.),
	and accumulate statistics.
*/

BOARD *newboard()
{
	BOARD *temp;

#if DEBUG_LEVEL > 0
	if(!freeboards)
#if DEBUG_LEVEL > 1
	{
		printf("Gotta grab more boards...\n");
		printf("Current boards outstanding : %d\n",boards_in_use);
		printf("           High-water mark : %d\n",max_used_boards);
#endif
		initfree();
#if DEBUG_LEVEL > 1
	}

	boards_in_use++;
	if(max_used_boards<boards_in_use)
		max_used_boards=boards_in_use;
#endif
#endif

	temp=freeboards;
	freeboards=freeboards->sons[0];
	temp->sons[0]=NULL;
	return(temp);
}

reclaim(board)
BOARD *board;
{
#if DEBUG_LEVEL > 1
	boards_in_use--;
#endif
#if DEBUG_LEVEL > 2
	if(board<board_bottom || board > board_end)
		printf("warning: attempted to reclaim non-board\n");
	else
	{
#endif

	board->sons[0]=freeboards;
	freeboards=board;

#if DEBUG_LEVEL > 2
	}
#endif

}

/*
	Shell sort taken from K&R, sorts the n boards in the array into ascending
	or descending order based on the global boolean max, sorting on the
	values contained in the value member of each board structure. This sort
	focuses the alphabeta search significantly, increasing the pruning enough
	to cut depth 4 search time by approximately 65 percent.
*/

sort(boards,n)
BOARD **boards;
int n;
{
	int i,
		j,
		gap,
		jpg; /* temporary storage hold j+gap */

	BOARD *tempboard;

	for(gap=n/2;gap>0;gap/=2)
		for(i=gap;i<n;i++)
			for(j=i-gap;j>=0 &&
					(max?(boards[j]->val<boards[jpg=j+gap]->val):
					(boards[j]->val>boards[jpg=j+gap]->val));j-=gap)
			{
				tempboard=boards[j];
				boards[j]=boards[jpg];
				boards[jpg]=tempboard;
			}
}

/*
	Initialize a linked list of free boards. Each board has an array of
	8 pointers to rows of 8 bytes each. Allocate space for the rows, and
	initialize the pointer arrays to point to the rows. The rows in a board
	are explicitly allocated contiguously, so it is possible (and turns out
	to enhance efficiency at the expense of comprehensability) to treat
	a board as a single array of 64 bytes, pointed to by the pointer to
	the first row. Optionally, produce statistics on allocation of memory.
*/

initfree()
{
	int i,j;

	char *calloc(),
		 *boardspace;

	freeboards=((BOARD *) calloc(maxboards,sizeof(BOARD)));
	if(!freeboards)
	{
		printf("The board structure allocation failed. Sorry, boss.\n");
		exit(0);
	}
	boardspace=calloc(maxboards,sizeof(char [64]));
	if(!boardspace)
	{
		printf("The board freespace allocation failed. Sorry, boss.\n");
		exit(0);
	}

#if DEBUG_LEVEL > 1
	printf("    board  space %u\n",((unsigned int) freeboards));
	printf("            thru %u\n",
			((unsigned int) (freeboards+maxboards)));
	printf("    board arrays %u\n",((unsigned int) boardspace));
	printf("            thru %u\n",
			((unsigned int) (boardspace+64*maxboards)));
#endif

	/* thread linked list and arrange the row pointer arrays */
	for(i=0;i<maxboards;i++)
	{
		freeboards[i-1].sons[0]=freeboards+i;
		for(j=0;j<8;j++)
			freeboards[i].array[j]=boardspace+64*i+8*j;
	}
	freeboards[maxboards-1].sons[0]=NULL;

#if DEBUG_LEVEL > 2
	board_end=freeboards+(maxboards-1);
	board_count+=maxboards;
#endif

	/* We might be called again, if he needs more boards */
	maxboards=10;
}

/*
	The array moves contains information about the shape of a board, in
	a fashion which simplifies the checking of loop conditions in the
	code which is examining a board for a move, and flipping the resulting
	pieces. Specifically, moves (which is a byte array because it needs
	no large numbers) is used as follows:
		moves[i][j][k] refers to the subscript of the
			k-th square, in the
			j-th direction, from the
			i-th square on the board.
	Moves is 64 long; moves[i] is variable length delimited by NULL; and
	moves[i][j] is variable length delimited by the value of i.
*/

initmoves()
{
	int i,
		j,
		k,
		l,
		m,
		n;

	char *calloc(),
		 **pointers,
		 *bytes;

	/* 484 and 2016 are computed by rote */
	pointers=((char **) calloc(484,sizeof(char **)));
	if(pointers==NULL)
	{
		printf("initmoves: cannot allocate pointers. Sorry, boss.\n");
		exit(0);
	}
	bytes=calloc(2016,sizeof(char));
	if(bytes==NULL)
	{
		printf("initmoves: cannot allocate bytes. Sorry, boss.\n");
		exit(0);
	}

#if DEBUG_LEVEL > 1
	printf("pointers  set to  %u\n",((unsigned int) pointers));
	printf("   bytes  set to  %u\n",((unsigned int) bytes));
#endif

	/* for each square on the board */
	for(i=0;i<8;i++) for(j=0;j<8;j++)
	{

		/* set the corresponding entry of moves to some free pointers */
		moves[i*8+j]=pointers;

		/* for each direction */
		for(k=(-1);k<2;k++) for(l=(-1);l<2;l++)
			if(k || l)	/* if neither k or l we aren't going anywhere */
			{
				*pointers=bytes; /* point to some free bytes */
				/* let m and n walk to the edge of the board */
				for(m=i+k,n=j+l;m>=0 && m<8 && n>=0 && n<8;m+=k,n+=l)
					(*bytes++)=m*8+n;
				if(m!=i+k || n!=j+l)
				/* then we managed to walk somewhere */
				{
					(*bytes++)=i*8+j;	/* terminate bytes list				*/
					pointers++;			/* get pointer for next direction	*/
				}
			}
		(*pointers++)=NULL;	/* terminate pointers list */
	}

#if DEBUG_LEVEL > 1
	printf("pointers left at %u\n",((unsigned int) pointers));
	printf("   bytes left at %u\n",((unsigned int) bytes));
#endif

}

#if DEBUG_LEVEL > 2
int check_moves()
{
	int i,
		chk1,
		chk2;

	char **ptr1,
		 *ptr2;

	chk1=chk2=0;
	for(i=0;i<64;i++)
		for(ptr1=moves[i];*ptr1;ptr1++)
			for(ptr2=(*ptr1);(*ptr2)!=i;ptr2++)
			{
				if(*ptr2<0 || *ptr2>63)
					printf("moves subscript out of range at i=%d sub=%d\n\7",i,*ptr2);
				chk2+=chk1^=(*ptr2);
			}
	return(chk1+chk2);
}

int count_boards()
{
	int i;

	BOARD *ptr;

	for(i=0,ptr=freeboards;ptr;i++,ptr=ptr->sons[0]);
	return(i);
}
#endif

/*
	allsons finds all sons for the board which is its parameter, sets the
	array of pointers to sons to point to new boards containing the resulting
	boards, sets the val member of each son board structure to the value as
	evaluated by worth, and sorts the sons in order, to focus the alphabeta
	search. It returns the number of sons it found.
*/

int allsons(pos)
BOARD *pos;
{
	int cur=0, /* son next to allocate */
		i;

	char mine,			/* mine, from the point of the current player	*/
		 hisn,			/* likewise										*/
		 whose,			/* temporary variable--keep from recomputing	*/
		 *board,		/* pointer into the board array					*/
		 ***move_ptr,	/* pointer into the moves array					*/
		 **dir_ptr,		/* pointer into moves[i] arrays of directions	*/
		 *sub_ptr;		/* pointer into moves[i][j] arrays of subscrtips*/

	BOARD *resultof(),	/* create a board resulting from making a move	*/
		  *curson;		/* point to current son							*/

#if DEBUG_LEVEL > 1
	allsons_called++;
#endif

	mine=max?MINE:HIS;
	hisn=max?HIS:MINE;
	board=pos->array[0];

	/* for(i=0;i<64;i++) with move_ptr=moves[i] */
	for(i=0,move_ptr=moves;i<64;i++,move_ptr++)
	{
		/* if(board[i]==EMPTY) */
		if(!board[i])
			/* for(j=0;moves[i][j]!=NULL;j++) with sub_ptr=moves[i][j] */
			for(dir_ptr=(*move_ptr);sub_ptr=(*dir_ptr++);)
				/* if he owns the cell in the j-th direction */
				if(board[*sub_ptr++]==hisn)
				{
					/* scan until edge of board or end of list */
					/*
						NOTE: moves[i][j] is delimited by i, so the edge of
						the board looks like a cell containing the same thing
						as board[i], which must be empty if I got into this
						code; therefore, hitting edge of board looks just
						like seeing a space at the end of the string of
						opponents pieces, which means I cannot capture them.
					*/
					while((whose=board[*sub_ptr++])==hisn);
					if(whose==mine) /* then we have a possible capture */
					{
						curson=pos->sons[cur++]=resultof(pos,i);
						curson->val=(*worth)(curson);
						goto endit;	/* don't look in other directions */
					}
				}
endit:	;
	}

#if DEBUG_LEVEL > 0
	if(cur>MAXSONS)
	{
		fprintf(stderr,"allsons: I needed %d sons for",cur+1);
		putboard(pos,NULL);
		fprintf(stderr,"allsons: but I only am alotted %d.\n",MAXSONS);
		printf("Sorry, boss.\n");
		exit(0);
	}
#endif
#if DEBUG_LEVEL > 1
	if(greatest_branching < cur)
		greatest_branching=cur;
#endif

	sort(pos->sons,cur);
	pos->sons[cur]=0;
	return(cur);
}

/*
	Resultof makes a copy of the board (using _move(), a fast block
	move routine that comes with Mark DeSmet's Cware C compiler, if
	the code is being generated for an IBM-PC) and flips all squares
	thet need to be flipped based on making a move at position x
	(where x ranges for 0 to 63), takes the square at x, and returns
	a pointer to the resulting board. It calls newboard(), the free
	board server.
*/

BOARD *resultof(father,x)
BOARD *father;
int x;
{
	int mine,	/* mine, from the point of view of the current player	*/
		hisn;	/* likewise												*/

	char *board,	/* pointer into the board array						*/

#ifndef IBMPC
		 *tmpptr,	/* pointers for copying the board in portble C		*/
		 *tmplim,
#endif

		 **dir,	/* pointer for moves[x][j], a direction					*/
		 *sub;	/* pointer to a subscript, moves[i][j][k]				*/

	BOARD *newboard(),
		  *temp;

	mine=max?MINE:HIS;
	hisn=max?HIS:MINE;
	temp=newboard();

	/* Copy the board. Use a block move on the PC	*/
#ifdef IBMPC
	_move(64,father->array[0],temp->array[0]);
#else
	board=temp->array[0];
	tmpptr=father->array[0];
	tmplim=board+64;
	while(board<tmplim)
		(*board++)=(*tmpptr++);
#endif

	board=temp->array[0];

	/* for(j=0;moves[x][j]!=NULL;j++) */
	for(dir=moves[x];*dir;dir++)
		/* if the cell in the j-th direction is his  */
		if(board[**dir]==hisn)
		{
			sub=(*dir);

			/* scan as long as the pieces are his	*/
			/* (Please see discussion in allsons	*/
			while(board[*++sub]==hisn);

			/* if the search was terminated by a piece of mine */
			if(board[*sub]==mine)
			{
				/* do the same scan, flipping pieces as you go */
				sub=(*dir);
				while(board[*sub]==hisn)
					board[*(sub++)]=mine;
			}
		}

	/* put a piece where we actually moved */
	board[x]=mine;
	return(temp);
}

/*
	firstboard() returns a pointer to a board set up in the initial position.
	It is the only routine that actually zeros out a board array, and sets
	things up in it. The remainder of the boards are made by copying and
	then changing, by resultof(). The initial position is reversed if we
	are going first (because what is stored is not x's and o's, but MINE
	and HIS) and can be reversed again by a reverse switch.
*/

BOARD *firstboard()
{
	BOARD *temp,
		  *newboard();

	int i,
		j;

	temp=newboard();

	/* zero out the array */
	for(i=0;i<8;i++)
		for(j=0;j<8;j++)
			temp->array[i][j]=EMPTY;
	/* put the start position into the cells */
	/* either gofirst or reversed can switch the initialization */
	temp->array[3][3]=temp->array[4][4]=(!(gofirst^reversed))?MINE:HIS;
	temp->array[3][4]=temp->array[4][3]=(!(gofirst^reversed))?HIS:MINE;

#if DEBUG_LEVEL > 1
	temp->val=0;
#endif

	return(temp);
}

/*
	Getmove gets a move from the user. If the computer is an IBM-PC,
	the result is immediately displayed; otherwise, the user must wait
	for the computer to move. This is because of timing considerations;
	dumping a board into the video ram takes very little time, while
	cramming it through a 1200 baud line takes a fair while.
	There is complete checking for invalid input, but no verify or revise
	option (typo's will hurt you if they are legal moves).
*/

getmove(board)
BOARD **board;
{
	int i,
		j,
		k,
		n;

	char ans;

	BOARD *resultof(),
		  *temp;

	long time_tick();

	max=FALSE;

	/* if(<the number of sons found>==0) */
	if(!(n=allsons(*board)))
	{
		printf("You cannot move. My turn. Press return to continue: ");

#ifdef DeSmet
		scanf("\n");
#else
		while(getchar()!='\n');
#endif

		time=time_tick();
		return;
	}

	movenumber++;
	if(n==1)
	{
		printf("You have only one move. Press return to continue: ");

#ifdef DeSmet
		scanf("\n");
#else
		while(getchar()!='\n');
#endif

		time=time_tick();
		temp=(*board)->sons[0];

#if DEBUG_LEVEL > 1
		temp->val=worth(temp);
#endif

#ifdef IBMPC
		line_number=BOARD_TOP;
		putboard(temp,(*board));
#endif

		reclaim(*board);
		(*board)=temp;
		return;
	}

	/* get and validity check move */
retry:
	printf("Please input next move: ");
	scanf("%c%d",&ans,&i);
	time=time_tick();

#ifndef DeSmet
	while(getchar()!='\n');
#endif

	i--;
	j=tolower(ans)-'a';
	/* if(<position is out of range> || board[i][j]!=EMPTY) */
	if(i<0 || i>7 || j<0 || j>7 || (*board)->array[i][j])
	{
		printf("try again, numbnut.\n");
		goto retry;
	}
	/* scan the sons list, looking for a son with this cell occupied	*/
	for(k=0;!((*board)->sons[k]->array[i][j]);)
		/* if we have reached the end of the list without finding one	*/
		if(++k==n)
		{
			printf("try again, numbnut.\n");
			goto retry;
		}

	/* clean up stray sons */
	for(i=0;i<n;i++)
		if(i!=k)
			reclaim((*board)->sons[i]);
	temp=(*board)->sons[k];

#if DEBUG_LEVEL > 1
	temp->val=worth(temp);
#endif

#ifdef IBMPC
	line_number=BOARD_TOP;
	putboard(temp,(*board));
#endif

	reclaim(*board);
	*board=temp;
}

/*
	Score simply adds up the number of cells owned by each player,
	reports the results, and leaves.
*/

score(board)
BOARD *board;
{
	char i,
		 sums[3]={0,0,0},
		 *ptr;

	ptr=board->array[0];
	for(i=0;i<64;i++)
		sums[*ptr++]++;
	printf("I got %d; You got %d; %s.\n",sums[MINE],sums[HIS],
			sums[MINE]>sums[HIS]?"I win":
			(sums[MINE]==sums[HIS]?"The game is a draw":"You win"));
}

#ifdef IBMPC

/*
	Fast output routines for the IBM-PC. These use _lmove(), an intersegment
	block move subroutine that comes with the DeSmet C compiler.

	Fast_puts(s) moves the string which is its operand, delimited by
	return, newline, NULL, or any other non-printing character, and puts
	it into the video ram.
*/

fast_puts(s)
char *s;
{
	int i;

	/*
		since the character bytes in the video ram are interleaved with
		attribute bytes:
		for(i=0;s[i]>'\n';i++)
			scr_line[2*i]=s[i];
	*/
	for(i=0;(scr_line[i<<1]=s[i])>'\n';i++);

	/* and pad with blanks */
	while(i<80)
		scr_line[i++<<1]=' ';
	/* now shove the line out, pronto */
	_lmove(160,scr_line,_showds(),line_number,screen_seg);
	/* increment the video ram line offset */
	line_number+=160;
}

/* clear the top part of the screen, and home the cursor */
clear_home()
{
	int i;

	/* make a blank video line */
	for(i=0;i<80;scr_line[i++<<1]=' ');

	/* and run it out */
	for(line_number=0;line_number<BOARD_TOP;line_number+=160)
		_lmove(160,scr_line,_showds(),line_number,screen_seg);

#asm
	mov	ah,15	; function number to read video page
	int	10h		; rom bios call to make a video function request
	mov	dx,0	; dh=dl=0 for top right-hand corner
	mov	ah,2	; function number for cursor positioning
	int	10h		; rom bios call to make a video function request
#
}

/*
	Grab a representative line out of the video ram, to get the current
	attribute bytes.
*/

init_screen()
{
	int monochrome;

#asm
	push	ds			; save data segment
	mov		ax,40h		; load hex 40
	mov		ds,ax		; into data segment
	mov		di,[10h]	; get equipment flags
	pop		ds			; restore data segment
	and		di,30h		; check for monochrome board
	mov		[bp-2],di	; put value in local monochrome
#
	screen_seg=(monochrome==0x30)?0xb000:0xb800;
	_lmove(160,0,screen_seg,scr_line,_showds());
}

#else

/*
	by careful design, fast_puts() is functionally equivalent to printf
*/

#define fast_puts printf

#endif

/*
	Putboard can be used for one or two boards. For one board, make the
	second parameter NULL. It calls a function fast_puts to put the string
	out. This is to allow quick board drawing on a PC.
	Optionally, error checking code can be compiled in, to check for the
	(common) C bug of wandering of into randomn memory locations.
	Throughout the function, realize the "if(new)" is functionally identical
	to "if(new!=NULL)".
*/

putboard(old,new)
BOARD *old,
	  *new;
{
	int i,
		j,
		k;

	char s[80];

#ifdef IBMPC
	line_number=BOARD_TOP; /* offset of top of board */
#endif

	if(new)
		fast_puts("      a   b   c   d   e   f   g   h        a   b   c   d   e   f   g   h\n");
	else
		fast_puts("      a   b   c   d   e   f   g   h\n");

	/* for every row */
	for(i=0;i<8;i++)
	{
		k=0;
		if(new)
			fast_puts("    ---------------------------------    ---------------------------------\n");
		else
			fast_puts("    ---------------------------------\n");
		sprintf(s,"  %d | ",i+1);
		while(s[++k]);

		/* for every column in the first board */
		for(j=0;j<8;j++)
		{

#if DEBUG_LEVEL > 0
			if(old->array[i][j]<0 || old->array[i][j]>2)
			{
				printf("putboard: garbage in cell %d %d--exiting...\n",i,j);
				exit(0);
			}
#endif

			s[k++]=print_chars[old->array[i][j]];
			s[k++]=' ';
			s[k++]='|';
			s[k++]=' ';
		}

		if(new)
		{
			sprintf(s+k," %d | ",i+1);
			while(s[++k]);

			/* for every column in the second board */
			for(j=0;j<8;j++)
			{

#if DEBUG_LEVEL > 0
				if(new->array[i][j]<0 || old->array[i][j]>2)
				{
					printf("putboard: garbage in cell %d %d--exiting...\n",i,j);
					exit(0);
				}
#endif

				s[k++]=print_chars[new->array[i][j]];
				s[k++]=' ';
				s[k++]='|';
 				s[k++]=' ';
			}

		}
		s[k++]='\n';
		s[k]='\0';
		fast_puts(s);
	}

	if(new)
		fast_puts("    ---------------------------------    ---------------------------------\n");
	else
		fast_puts("    ---------------------------------\n");

#if DEBUG_LEVEL > 1
	if(new)
		sprintf(s,"                  %d                                     %d\n",
				old->val,new->val);
	else
		sprintf(s,"                  %d\n",old->val);
	fast_puts(s);
#endif
}

/*
	Worth_1 is the worth function containing all the subtle strategic
	heuristic information in the game. It is used until we can start
	looking all the way to the end of the game, at which point the
	optimum heuristic function, h* becomes available. That is called
	worth_2, and is much simpler.
*/

worth_1(board)
BOARD *board;
{
	int valsum[3]; /* buckets in which to accumulate the sums		*/

	char *ptr,	/* temporary pointers for walking through the array	*/
		 *t;

	static char
		val1[3]={30,0,0},	/* value of (1,1) if (0,0)=0,1,2 */
		val2[3]={ 4,0,0},	/* value of (1,2) if (0,2)=0,1,2 */
		val3[3]={ 5,0,0};	/* value of (1,3) if (0,3)=0,1,2 */

#define ev0	50	/* value of pos 00 (corner)		*/
#define ev1	4	/* value of pos 01				*/
#define ev2	16	/* value of pos 02				*/
#define ev3	12	/* value of pos 03				*/
#define sv	20	/* value of a split on the edge */

/*
	 50,  4, 16, 12, 12, 16,  4, 50,
	  4,-30, -4, -5, -5, -4,-30,  4,
	 16, -4,  1,  0,  0,  1, -4, 16,		This is what the board cell
	 12, -5,  0,  0,  0,  0, -5, 12,		worth function looks like,
	 12, -5,  0,  0,  0,  0, -5, 12,		discounting all dynamic
	 16, -4,  1,  0,  0,  1, -4, 16,		dependancies.
	  4,-30, -4, -5, -5, -4,-30,  4,
	 50,  4, 16, 12, 12, 16,  4, 50
*/

/*
	f[] is a finite state automaton used for edge strategy
	It recognizes two related phenomena, which we call "splits";
	positions where two pieces owned by one player on an edge are

		a) separated by exactly 1 blank, or
		b) separated by 1 or more of the opponent's

	Invented by John White, it is structured as follows:

	f[105] can be viewed as 5 tiers of 7 states, each of which requires
	3 cells for the three possible input values.
	Starting at one corner, you scan along an edge.
	Keep always in mind that the values of board cells are

						0		EMPTY
						1		MINE
						2		HIS

	The states are numbered as follows:

	  state			decription						board
	  -----	----------------------------------		------

		0	currently scanning through blanks		... 0
		1	just seen a square of mine				... 1
		2	just seen a square if his				... 2
		3	a blank following a square of mine		... 10
		4	a blank following a square of his		... 20
		5	one of his following one of mine		... 12
		6	one of mine following one of his		... 21

	The following table identifies the transitions between states.
	The numbers down the left, labelling the rows, are the input
	cell values. The numbers across the top are state numbers.
	The contents of a cell in this matrix is the number of the
	state the will be result from the input at the left from the
	state above.

			0		1		2		3		4		5		6
		---------------------------------------------------------
	0	|	0	|	3	|	4	|	0	|	0	|	4	|	3	|
		---------------------------------------------------------
	1	|	1	|	1	|	6	|	1 -	|	1	|	6 -	|	6	|
		---------------------------------------------------------
	2	|	2	|	5	|	2	|	2	|	2 +	|	5	|	5 +	|
		---------------------------------------------------------

	The cells containing postfix "+" or "-" symbols represent
	situations in which we have found one of the key patterns,
	at which point we go to the state indicated in the immediately
	higher or lower tier, respectively. The final value is
	simply the number of the tier we are on at the end, multiplied
	by sv, the split value. Note that each state takes three array elements,
	so the actual contents of the array are three times the state
	numbers shown above, repeated 5 times, offset by the tier start
	subscripts, with special offsets applied to the cells which
	jump tiers. The array v[] is used for the last lookup, since
	we are uninterested in the exact state, but just the tier, and
	since the tier number must be multiplied by sv, we put the resulting
	products in v[]. Finally, the tiers are organized as follows:

			  offset	meaning			    value
			  ------ ----------------	    -----
		
				 0		 neutral			   0
				21		  good				  sv
				42		  bad				 -sv
				63		very good			 2*sv
				84		very bad			-2*sv

	With this organization, if the state of the machine at time t0 is
	S0 and the input is I0, the state at time t1 is f[S0+I0], and therefore
	the state at time t2 is f[f[S0+I0]+I1] and so forth.
	So, without further ado:
*/

	static char f[105]=
				{
/*----------------------------------------------------------------------------
|state    0		 	1		   2		 3		   4		  5			 6   |
|input 0  1  2   0  1  2   0   1  2   0  1  2   0  1  2   0   1  2   0   1  2|
----------------------------------------------------------------------------*/
	   0, 3, 6,  9, 3,15, 12, 18, 6,  0,45, 6,  0, 3,27, 12, 60,15,  9, 18,36,
	  21,24,27, 30,24,36, 33, 39,27, 21, 3,27, 21,24,69, 33, 18,36, 30, 39,78,
	  42,45,48, 51,45,57, 54, 60,48, 42,87,48, 42,45, 6, 54,102,57, 51, 60,15,
	  63,66,69, 72,66,78, 75, 81,69, 63,24,69, 63,66,69, 75, 39,78, 72, 81,78,
	  84,87,90, 93,87,99, 96,102,90, 84,87,90, 84,87,48, 96,102,99, 93,102,57
				};

/* v is the final pass of f, and is board value instead of next state */

	static int v[105]=
			   {
		0,0,0,0,0,0,0,0,0,0,-sv,0,0,0,sv,0,-sv,0,0,0,sv,
		sv,sv,sv,sv,sv,sv,sv,sv,sv,sv,0,sv,sv,sv,2*sv,sv,0,sv,sv,sv,2*sv,
		-sv,-sv,-sv,-sv,-sv,-sv,-sv,-sv,-sv,-sv,-2*sv,-sv,-sv,-sv,0,-sv,
				-2*sv,-sv,-sv,-sv,0,
		2*sv,2*sv,2*sv,2*sv,2*sv,2*sv,2*sv,2*sv,2*sv,2*sv,sv,2*sv,2*sv,
				2*sv,2*sv,2*sv,sv,2*sv,2*sv,2*sv,2*sv,
		-2*sv,-2*sv,-2*sv,-2*sv,-2*sv,-2*sv,-2*sv,-2*sv,-2*sv,-2*sv,-2*sv,
				-2*sv,-2*sv,-2*sv,-sv,-2*sv,-2*sv,-2*sv,-2*sv,-2*sv,-sv
			   };

#if DEBUG_LEVEL > 1
	worth_called++;
#endif

	*valsum=valsum[2]=0;	/* clean out buckets	*/
	ptr=t=board->array[0];	/* set up pointers		*/

	/* and let the finite state automoton roll--one edge in each term */
	valsum[1]=
	  v[f[f[f[f[f[f[f[  *t ]+t[ 1]]+t[ 2]]+t[ 3]]+t[ 4]]+t[ 5]]+t[ 6]]+t[ 7]]
	 +v[f[f[f[f[f[f[f[  *t ]+t[ 8]]+t[16]]+t[24]]+t[32]]+t[40]]+t[48]]+t[56]]
	 +v[f[f[f[f[f[f[f[t[ 7]]+t[15]]+t[23]]+t[31]]+t[39]]+t[47]]+t[55]]+t[63]]
	 +v[f[f[f[f[f[f[f[t[56]]+t[57]]+t[58]]+t[59]]+t[60]]+t[61]]+t[62]]+t[63]];

	/*
		if the worth array shown in the comment above actually existed, the
		next 60 or so lines might have been written

			for(i=0;i<64;i++)
				valsum[board[i]]+=worth[i];

		but it doesn't, except in the defined constants ev0 through ev3.
		Besides, it's quicker to execute 60 statements than to go through
		a loop 60 times (no loop control and branching) and this function
		is at the bottom of the recursion, and needs to be fast.
	*/

	valsum[*ptr++]+=ev0;
	valsum[*ptr++]+=ev1;
	valsum[*ptr++]+=ev2;
	valsum[*ptr++]+=ev3;
	valsum[*ptr++]+=ev3;
	valsum[*ptr++]+=ev2;
	valsum[*ptr++]+=ev1;
	valsum[*ptr++]+=ev0;

	valsum[*ptr++]+=ev1;
	valsum[*ptr++]-=val1[*t];
	valsum[*ptr++]-=val2[t[2]];
	valsum[*ptr++]-=val3[t[3]];
	valsum[*ptr++]-=val3[t[4]];
	valsum[*ptr++]-=val2[t[5]];
	valsum[*ptr++]-=val1[t[7]];
	valsum[*ptr++]+=ev1;

	valsum[*ptr++]+=ev2;
	valsum[*ptr++]-=val2[t[16]];
	valsum[*ptr]++;
	ptr+=3;
	valsum[*ptr++]++;
	valsum[*ptr++]-=val2[t[23]];
	valsum[*ptr++]+=ev2;

	valsum[*ptr++]+=ev3;
	valsum[*ptr]-=val3[t[24]];
	ptr+=5;
	valsum[*ptr++]-=val3[t[31]];
	valsum[*ptr++]+=ev3;

	valsum[*ptr++]+=ev3;
	valsum[*ptr]-=val3[t[32]];
	ptr+=5;
	valsum[*ptr++]-=val3[t[39]];
	valsum[*ptr++]+=ev3;

	valsum[*ptr++]+=ev2;
	valsum[*ptr++]-=val2[t[40]];
	valsum[*ptr]++;
	ptr+=3;
	valsum[*ptr++]++;
	valsum[*ptr++]-=val2[t[47]];
	valsum[*ptr++]+=ev2;

	valsum[*ptr++]+=ev1;
	valsum[*ptr++]-=val1[t[56]];
	valsum[*ptr++]-=val2[t[58]];
	valsum[*ptr++]-=val3[t[59]];
	valsum[*ptr++]-=val3[t[60]];
	valsum[*ptr++]-=val2[t[61]];
	valsum[*ptr++]-=val1[t[63]];
	valsum[*ptr++]+=ev1;

	valsum[*ptr++]+=ev0;
	valsum[*ptr++]+=ev1;
	valsum[*ptr++]+=ev2;
	valsum[*ptr++]+=ev3;
	valsum[*ptr++]+=ev3;
	valsum[*ptr++]+=ev2;
	valsum[*ptr++]+=ev1;
	valsum[*ptr]+=ev0;

	return(valsum[1]-valsum[2]);
}

/*
	If worth_2 is being called, we are looking all the way to the end of
	the game, and we can use the final board as an evaluator: the worth
	of the board is the number of squares more I have than he. This number
	is shifted left 2 to attempt to make the range of values returned
	approximately comparable to worth_1, so that worth_2 can be used
	by alphabeta when we find an early game ending.
*/

worth_2(board)
BOARD *board;
{

	int valsum[3]={0,0,0};

	char *ptr;

#if DEBUG_LEVEL > 1
	worth_called++;
#endif

	ptr=board->array[0];
	/*
		The following 64 lines could have been replaced with
			for(i=0;i<64;i++)
				valsum[board[i]]++;

		but it would have been slower.
	*/
	valsum[*ptr++]++;
	valsum[*ptr++]++;
	valsum[*ptr++]++;
	valsum[*ptr++]++;
	valsum[*ptr++]++;
	valsum[*ptr++]++;
	valsum[*ptr++]++;
	valsum[*ptr++]++;
	valsum[*ptr++]++;
	valsum[*ptr++]++;
	valsum[*ptr++]++;
	valsum[*ptr++]++;
	valsum[*ptr++]++;
	valsum[*ptr++]++;
	valsum[*ptr++]++;
	valsum[*ptr++]++;
	valsum[*ptr++]++;
	valsum[*ptr++]++;
	valsum[*ptr++]++;
	valsum[*ptr++]++;
	valsum[*ptr++]++;
	valsum[*ptr++]++;
	valsum[*ptr++]++;
	valsum[*ptr++]++;
	valsum[*ptr++]++;
	valsum[*ptr++]++;
	valsum[*ptr++]++;
	valsum[*ptr++]++;
	valsum[*ptr++]++;
	valsum[*ptr++]++;
	valsum[*ptr++]++;
	valsum[*ptr++]++;
	valsum[*ptr++]++;
	valsum[*ptr++]++;
	valsum[*ptr++]++;
	valsum[*ptr++]++;
	valsum[*ptr++]++;
	valsum[*ptr++]++;
	valsum[*ptr++]++;
	valsum[*ptr++]++;
	valsum[*ptr++]++;
	valsum[*ptr++]++;
	valsum[*ptr++]++;
	valsum[*ptr++]++;
	valsum[*ptr++]++;
	valsum[*ptr++]++;
	valsum[*ptr++]++;
	valsum[*ptr++]++;
	valsum[*ptr++]++;
	valsum[*ptr++]++;
	valsum[*ptr++]++;
	valsum[*ptr++]++;
	valsum[*ptr++]++;
	valsum[*ptr++]++;
	valsum[*ptr++]++;
	valsum[*ptr++]++;
	valsum[*ptr++]++;
	valsum[*ptr++]++;
	valsum[*ptr++]++;
	valsum[*ptr++]++;
	valsum[*ptr++]++;
	valsum[*ptr++]++;
	valsum[*ptr++]++;
	valsum[*ptr]++;

	/* return((<number I have> - <number he has>) * 2); */
	return((valsum[1]-valsum[2])<<2);
}

#ifdef IBMPC

/*
	Time_tick returns the (long) number of 100'ths of seconds since
	the day began, according to the PC's real-time clock. This is
	useful for getting elapsed time by subtracting successive times.
*/

long time_tick()
{
#asm
	mov	ah,2ch	; function number for get time-of-day
	int 21h		; make DOS function call
	xor ah,ah	; zero ah
	mov al,ch	;
	mov bl,60	; ax=60*ch
	mul bl		;
	xor ch,ch	; zero ch
	add cx,ax	; cx=60*ch + cl is minutes
	xor ah,ah	; zero ah
	mov al,dh	;
	mov bl,100	; ax=100*dh
	mul bl		;
	xor dh,dh	; zero dh
	add dx,ax	; dx=100*dh + dl is hundredths of seconds
	mov bx,dx	; stash it in bx
	xor dx,dx	; freeing up dx
	mov ax,cx	; ax gets minutes
	mov cx,6000 ;
	mul cx		; times 6000 is hundredths of seconds in ax and dx
	add ax,bx	; plus hundredths of seconds
	jae	done	; if no carry then we are done--calling convention for
				; long ints in c is to return them in dx & ax
	inc dx		; if carry, fixup dx
done:
#
}
#else

/* dummy routine for other systems */

long time_tick()
{
	return(0);
}
#endif


